package com.gitee.ywj1352.算法.week01;

/**
 * 字节特别喜欢考的题目
 * <p>
 * 给你一个链表，每k个节点一组进行翻转，请你返回翻转后的链表。
 * <p>
 * k是一个正整数，它的值小于或等于链表的长度。
 * <p>
 * 如果节点总数不是k的整数倍，那么请将最后剩余的节点保持原有顺序。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/reverse-nodes-in-k-group
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

public class K个一组翻转链表 {

    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode tail = head;
        for (int i = 0; i < k; i++) {
            if (tail == null) {
                return head;
            }
            tail = tail.next;
        }
        // 先翻转前 k 个节点
        ListNode newHead = reverse(head, tail);
        // 再递归翻转后续以 k 个节点为一组的子链表，并以 head.next 指向返回的子链表头结点，将链表连接起来
        head.next = reverseKGroup(tail, k);
        return newHead;
    }


    public ListNode reverseKGroup2(ListNode head, int k) {
        ListNode tail = head;
        for (int i = 0; i < k; i++) {
            if (tail == null) {
                return head;
            }
            tail = tail.next;
        }
        // |1-2-3|-4-5-6-7  -> |3-2-1|-4-5-6-7
        ListNode newHead = reverse(head, tail);
        //此时的head为1 head.next 为下一个反转好的数组
        head.next = reverseKGroup2(tail, k);
        return newHead;
    }


    /**
     * 翻转单链表中的一段，从 head 节点到该链表中的 end 节点（左闭右开：[head, end)]）
     */
    public ListNode reverse(ListNode head, ListNode end) {
        ListNode current = head;
        ListNode pre = null;
        while (current != end) {
            ListNode next = current.next;
            current.next = pre;
            pre = current;
            current = next;
        }
        return pre;
    }
}
